package com.leetcode.binary_search;

/**
 * @author Dennis Li
 * @date 2020/7/24 17:02
 */
public class SingleNonDuplicate_540 {

    public static int singleNonDuplicate(int[] nums) {
        int n = nums.length - 1;
        if(n + 1 == 1) return nums[0];
        int i = 0, j = n, mid = n >> 1;
        while (i < j) {
            mid = i + ((j - i) >> 1);
            if (nums[mid] == nums[mid + 1]) {
                int len = n - mid + 1;
                if ((len & 1) == 1) i = mid;
                else {
                    j = mid - 1;
                    if(j == 0 || nums[j] != nums[j - 1]) return nums[j];
                }
            } else if (nums[mid] == nums[mid - 1]) {
                int len = mid + 1;
                if ((len & 1) == 1) j = mid;
                else {
                    i = mid + 1;
                    if(i == n || nums[i] != nums[i + 1]) return nums[i];
                }
            } else break;
        }
        return nums[mid];
    }

}
